package com.kaizen.leet581;

import java.util.Arrays;

/**
 * 581. 最短无序连续子数组
 * 给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
 *
 * 你找到的子数组应是最短的，请输出它的长度。
 *
 * 示例 1:
 *
 * 输入: [2, 6, 4, 8, 10, 9, 15]
 * 输出: 5
 * 解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
 * 说明 :
 *
 * 输入的数组长度范围在 [1, 10,000]。
 * 输入的数组可能包含重复元素 ，所以升序的意思是<=。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author kaizen
 * @date 2020/6/9 20:43
 */
public class SolutionKaizen {

    /**
     * 参考官方思路，每次判断是否存在前面的元素比自己小，如果比自己小，则记录索引位置
     * @param nums
     * @return
     */
    public int findUnsortedSubarray(int[] nums) {
        int l = nums.length, r = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[i]) {
                    r = Math.max(r, j);
                    l = Math.min(l, i);
                }
            }
        }
        return r - l < 0 ? 0 : r - l + 1;
    }

    /**
     * 从右到左 找出右边界 右边界的所有值都是有序的
     * 从左到右 找出左边界 左边界所有值都是有序的
     * @param nums
     * @return
     */
    public int findUnsortedSubarray1(int[] nums) {
        if(nums == null || nums.length <= 0) {
            return 0;
        }
        if(nums.length == 1) {
            return 0;
        }
        int length = nums.length;
        int min = nums[length - 1];
        int max = nums[0];
        int l = length - 1;
        int r = 0;
        for (int i = 0; i < length; i++) {
            if (max > nums[i]) {
                r = Math.max(r, i);
            }else {
                max = nums[i];
            }
            if (min < nums[length - i - 1]) {
                l = Math.min(l, length - i - 1);
            }else {
                min = nums[length - i - 1];
            }
        }

        return r - l < 0 ? 0 : r - l + 1;
    }

    /**
     * 思路2
     * 先排序，再与排序后的数组对比
     *  作者：LeetCode
     *  链接：https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/solution/zui-duan-wu-xu-lian-xu-zi-shu-zu-by-leetcode/
     *  来源：力扣（LeetCode）
     *  著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    public int findUnsortedSubarray2(int[] nums) {
        int[] snums = nums.clone();
        Arrays.sort(snums);
        int start = snums.length, end = 0;
        for (int i = 0; i < snums.length; i++) {
            if (snums[i] != nums[i]) {
                start = Math.min(start, i);
                end = Math.max(end, i);
            }
        }
        return (end - start >= 0 ? end - start + 1 : 0);
    }





}
